/*******************************************************************************
* Copyright (c) 2000 John M Hanna
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*******************************************************************************/

/*
 * Code originally from http://sourceforge.net/projects/shop-js.  Relicensed
 * under the MIT license with permission from John M Hanna.
 */

// ---------------------- Arbitrary Precision Math
// badd(a,b), bsub(a,b), bmul(a,b), bdiv(a,b), bmod(a,b),
// brshift(a), beq(a,b)

// set the base... 32bit cpu -> bs=16, 64bit -> bs=32
// bm is the mask, bs is the shift
//bm=0xf; bs=4;  // low base useful for testing if digits handled ok
const hanna_bs = 28;
const hanna_bx2 = 1 << hanna_bs;
const hanna_bm = hanna_bx2 - 1;
const hanna_bx = hanna_bx2 >> 1;
const hanna_bd = hanna_bs >> 1;
const hanna_bdm = (1 << hanna_bd) - 1
const hanna_log2 = Math.log(2)

function badd( a, b ) // binary add
{
    const bs = hanna_bs;
    const bm = hanna_bm;
    var al = a.length, bl = b.length
    if (al < bl) return badd(b, a)
    var c = 0, r = [], n = 0
    for (; n < bl; n++)
    {
        c += a[n] + b[n]
        r[n] = c & bm
        c >>>= bs
    }
    for (; n < al; n++)
    {
        c += a[n]
        r[n] = c & bm
        c >>>= bs
    }
    if (c) r[n] = c
    return r
}

function beq( a, b ) // returns 1 if a == b
{
    if (a.length != b.length) return 0
    for (var n = a.length - 1; n >= 0; n--)
        if (a[n] != b[n]) return 0
    return 1
}

function bsub( a, b ) // binary subtract
{
    const bs = hanna_bs;
    const bm = hanna_bm;
    var al = a.length, bl = b.length, c = 0, r = []
    if (bl > al)
    {return []}
    if (bl == al)
    {
        if (b[bl - 1] > a[bl - 1]) return []
        if (bl == 1) return [a[0] - b[0]]
    }
    for (var n = 0; n < bl; n++)
    {
        c += a[n] - b[n]
        r[n] = c & bm
        c >>= bs
    }
    for (; n < al; n++)
    {
        c += a[n]
        r[n] = c & bm
        c >>= bs
    }
    if (c)
    {return []}
    if (r[n - 1]) return r
    while (n > 1 && r[n - 1] == 0) n--;
    return r.slice(0, n)
}
function bmul( a, b ) // binary multiply
{
    const bs = hanna_bs;
    const bm = hanna_bm;
    const bd = hanna_bd;
    const bdm = hanna_bdm;
    b = b.concat([0])
    var al = a.length, bl = b.length, r = [], n,nn,aa, c, m
    var g,gg,h,hh,ghh,ghhb

    for (n = al + bl; n >= 0; n--) r[n] = 0
    for (n = 0; n < al; n++)
    {
        if (aa = a[n])
        {
            c = 0
            hh = aa >> bd;
            h = aa & bdm
            m = n
            for (nn = 0; nn < bl; nn++,m++)
            {
                g = b[nn];
                gg = g >> bd;
                g = g & bdm
                //(gg*2^15 + g) * (hh*2^15 + h) = (gghh*2^30 + (ghh+hgg)*2^15 +hg)
                ghh = g * hh + h * gg
                ghhb = ghh >> bd;
                ghh &= bdm
                c += r[m] + h * g + (ghh << bd)
                r[m] = c & bm
                c = (c >> bs) + gg * hh + ghhb
            }
        }
    }
    n = r.length
    if (r[n - 1]) return r
    while (n > 1 && r[n - 1] == 0) n--;
    return r.slice(0, n)
}

function blshift( a, b )
{
    const bs = hanna_bs;
    const bm = hanna_bm;
    var n, c = 0, r = []
    for (n = 0; n < a.length; n++)
    {
        c |= (a[n] << b)
        r[n] = c & bm
        c >>= bs
    }
    if (c) r[n] = c
    return r
}

function brshift( a )
{
    const bs = hanna_bs;
    var c = 0,n,cc, r = []
    for (n = a.length - 1; n >= 0; n--)
    {
        cc = a[n];
        c <<= bs
        r[n] = (cc | c) >> 1
        c = cc & 1
    }
    while (r.length > 1 && r[r.length - 1] == 0)
    {
        r = r.slice(0, -1)
    }
    this.a = r;
    this.c = c
    return this
}

function zeros( n )
{
    var r = [];
    while (n-- > 0)
        r[n] = 0;
    return r
}

function toppart( x, start, len )
{
    const bx2 = hanna_bx2;
    var n = 0
    while (start >= 0 && len-- > 0)
        n = n * bx2 + x[start--]
    return n
}

//14.20 Algorithm Multiple-precision division from HAC
function bdiv( x, y )
{
    const bs = hanna_bs;
    const bm = hanna_bm;
    var n = x.length - 1, t = y.length - 1, nmt = n - t, q;
     // trivial cases; x < y
    if (n < t || n == t && (x[n] < y[n] || n > 0 && x[n] == y[n] && x[n - 1] < y[n - 1]))
    {
        this.q = [0];
        this.mod = x;
        return this
    }
    // trivial cases; q < 4
    if (n == t && toppart(x, t, 2) / toppart(y, t, 2) < 4)
    {
        q = 0;
        var xx;
        for (; ;)
        {
            xx = bsub(x, y)
            if (xx.length == 0) break
            x = xx;
            q++
        }
        this.q = [q];
        this.mod = x;
        return this
    }
    var shift, shift2
    // normalize
    shift2 = Math.floor(Math.log(y[t]) / hanna_log2) + 1
    shift = bs - shift2
    if (shift)
    {
        x = x.concat();
        y = y.concat()
        for (i = t; i > 0; i--) y[i] = ((y[i] << shift) & bm) | (y[i - 1] >> shift2);
        y[0] = (y[0] << shift) & bm
        if (x[n] & ((bm << shift2) & bm))
        {
            x[++n] = 0;
            nmt++;
        }
        for (i = n; i > 0; i--) x[i] = ((x[i] << shift) & bm) | (x[i - 1] >> shift2);
        x[0] = (x[0] << shift) & bm
    }
    var i, x2, y2;
    q = zeros(nmt + 1)

    y2 = zeros(nmt).concat(y)
    for (; ;)
    {
        x2 = bsub(x, y2)
        if (x2.length == 0) break
        q[nmt]++
        x = x2
    }
    var yt = y[t], top = toppart(y, t, 2)
    for (i = n; i > t; i--)
    {
        var m = i - t - 1
        if (i >= x.length)
            q[m] = 1
        else if (x[i] == yt)
            q[m] = bm
        else
            q[m] = Math.floor(toppart(x, i, 2) / yt)

        var topx = toppart(x, i, 3)
        while (q[m] * top > topx)
            q[m]--
        //x-=q[m]*y*b^m
        y2 = y2.slice(1)
        x2 = bsub(x, bmul([q[m]], y2))
        if (x2.length == 0)
        {
            q[m]--
            x2 = bsub(x, bmul([q[m]], y2))
        }
        x = x2
    }
    // de-normalize
    if (shift)
    {
        for (i = 0; i < x.length - 1; i++) x[i] = (x[i] >> shift) | ((x[i + 1] << shift2) & bm);
        x[x.length - 1] >>= shift
    }
    while (q.length > 1 && q[q.length - 1] == 0) q = q.slice(0, q.length - 1)
    while (x.length > 1 && x[x.length - 1] == 0) x = x.slice(0, x.length - 1)
    this.mod = x
    this.q = q
    return this
}

function bmod( p, m )
{ // binary modulo
    const bdm = hanna_bdm;
    if (m.length == 1)
    {
        if (p.length == 1) return [p[0] % m[0]]
        if (m[0] < bdm) return [simplemod(p, m[0])]
    }

    var r = bdiv(p, m)
    return r.mod
}
function simplemod( i, m )
{
    const bd = hanna_bd;
    const bdm = hanna_bdm;
    // returns the mod where m < 2^bd
    var c = 0, v
    for (var n = i.length - 1; n >= 0; n--)
    {
        v = i[n]
        c = ((v >> bd) + (c << bd)) % m
        c = ((v & bdm) + (c << bd)) % m
    }
    return c
}
function bmodexp( xx, y, m )
{ // binary modular exponentiation
    const bs = hanna_bs;
    var r = [1], n, an,a, x = xx.concat()
    var mu = []
    n = m.length * 2;
    mu[n--] = 1;
    for (; n >= 0; n--) mu[n] = 0;
    mu = bdiv(mu, m).q

    for (n = 0; n < y.length; n++)
    {
        for (a = 1,an = 0; an < bs; an++,a <<= 1)
        {
            if (y[n] & a) r = bmod2(bmul(r, x), m, mu)
            x = bmod2(bmul(x, x), m, mu)
        }
    }
    return r
}

function bmod2( x, m, mu ) // Barrett's modular reduction from HAC, 14.42, CRC Press
{
    var xl = x.length - (m.length << 1)
    if (xl > 0)
    {
        return bmod2(x.slice(0, xl).concat(bmod2(x.slice(xl), m, mu)), m, mu)
    }
    var ml1 = m.length + 1, ml2 = m.length - 1,rr
    //var q1=x.slice(ml2)
    //var q2=bmul(q1,mu)
    var q3 = bmul(x.slice(ml2), mu).slice(ml1)
    var r1 = x.slice(0, ml1)
    var r2 = bmul(q3, m).slice(0, ml1)
    var r = bsub(r1, r2)
    //var s=('x='+x+'\nm='+m+'\nmu='+mu+'\nq1='+q1+'\nq2='+q2+'\nq3='+q3+'\nr1='+r1+'\nr2='+r2+'\nr='+r);
    if (r.length == 0)
    {
        r1[ml1] = 1
        r = bsub(r1, r2)
    }
    for (var n = 0; ; n++)
    {
        rr = bsub(r, m)
        if (rr.length == 0) break
        r = rr
        if (n >= 3) return bmod2(r, m, mu)
    }
    return r
}

function sub2( a, b )
{
    var r = bsub(a, b)
    if (r.length == 0)
    {
        this.a = bsub(b, a)
        this.sign = 1
    }
    else
    {
        this.a = r
        this.sign = 0
    }
    return this
}

function signedsub( a, b )
{
    if (a.sign)
    {
        if (b.sign)
        {
            return sub2(b, a)
        }
        else
        {
            this.a = badd(a, b)
            this.sign = 1
        }
    }
    else
    {
        if (b.sign)
        {
            this.a = badd(a, b)
            this.sign = 0
        }
        else
        {
            return sub2(a, b)
        }
    }
    return this
}

function modinverse( x, n ) // returns x^-1 mod n
{
    // from  Bryan Olson <bryanolson@my-deja.com>
    var y = n.concat(), t, r, bq, a = [1], b = [0], ts, q
    a.sign = 0;
    b.sign = 0
    while (y.length > 1 || y[0])
    {
        t = y.concat()
        r = bdiv(x, y)
        y = r.mod
        q = r.q
        x = t
        t = b.concat();
        ts = b.sign
        bq = bmul(b, q)
        bq.sign = b.sign
        r = signedsub(a, bq)
        b = r.a;
        b.sign = r.sign
        a = t;
        a.sign = ts
    }
    if (beq(x, [1]) == 0) return [0] // No inverse; GCD is x
    if (a.sign)
    {
        a = bsub(n, a)
    }
    return a
}

function crt_RSA( m, d, p, q )
{
    // Compute m**d mod p*q for RSA private key operations. -- Bryan Olson via deja.com
    var xp = bmodexp(bmod(m, p), bmod(d, bsub(p, [1])), p)
    var xq = bmodexp(bmod(m, q), bmod(d, bsub(q, [1])), q)
    var t = bsub(xq, xp);
    if (t.length == 0)
    {
        t = bsub(xp, xq)
        t = bmod(bmul(t, modinverse(p, q)), q);
        t = bsub(q, t)
    }
    else
    {
        t = bmod(bmul(t, modinverse(p, q)), q);
    }
    return badd(bmul(t, p), xp)
}

// conversion functions:
// text to binary and binary to text, text to base64 and base64 to text
// OK, so this isn't exactly base64 -- fix it if you care

function t2b( s )
{
    const bm = hanna_bm;
    var bits = s.length * 8, bn = 1, r = [0], rn = 0, sn = 0, sb = 1;
    var c = s.charCodeAt(0)
    for (var n = 0; n < bits; n++)
    {
        if (bn > bm)
        {
            bn = 1;
            r[++rn] = 0;
        }
        if (c & sb)  r[rn] |= bn;
        bn <<= 1
        if ((sb <<= 1) > 255)
        {
            sb = 1;
            c = s.charCodeAt(++sn);
        }
    }
    return r;
}

function b2t( b )
{
    const bs = hanna_bs;
    const bm = hanna_bm;
    var bits = b.length * bs, bn = 1, bc = 0, r = [0], rb = 1, rn = 0
    for (var n = 0; n < bits; n++)
    {
        if (b[bc] & bn) r[rn] |= rb;
        if ((rb <<= 1) > 255)
        {
            rb = 1;
            r[++rn] = 0;
        }
        if ((bn <<= 1) > bm)
        {
            bn = 1;
            bc++;
        }
    }
    while (r[rn] == 0)
    {rn--;}
    var rr = ''
    for (n = 0; n <= rn; n++)
        rr += String.fromCharCode(r[n]);
    return rr;
}

// RC4 stream encryption
// adapted from www.cpan.org crypt::rc4 -- thanks!
function rc4( key, text )
{
    var i, x, y, t, x2, kl = key.length;
    var s = [];

    for (i = 0; i < 256; i++) s[i] = i
    y = 0
    for (var j = 0; j < 2; j++)
    {
        for (x = 0; x < 256; x++)
        {
            y = (key.charCodeAt(x % kl) + s[x] + y) % 256
            t = s[x];
            s[x] = s[y];
            s[y] = t
        }
    }
    var z = ""
    for (x = 0; x < text.length; x++)
    {
        x2 = x & 255
        y = ( s[x2] + y) & 255
        t = s[x2];
        s[x2] = s[y];
        s[y] = t
        z += String.fromCharCode((text.charCodeAt(x) ^ s[(s[x2] + s[y]) % 256]))
    }
    return z
}

function ror( a, n )
{
    n &= 7;
    return n ? ((a >> n) | ((a << (8 - n)) & 255)) : a;
}
/*

function hash( s, l )
{
    var sl = s.length,r = [],rr = '',v = 1,lr = 4;
    for (var n = 0; n < l; n++) r[n] = (v = ((v * v * 5081 + n) & 255));
    while (sl--)
    {
        lr = r[sl % l] ^= ror(s.charCodeAt(sl), lr) ^ r[r[(sl * 5081) % l] % l];
    }
    for (n = 0; n < l; n++)
        rr += String.fromCharCode(r[n] ^
                                  ror(r[r[(n * 171) % l] % l], r[n]));
    return rr
}

// seed the random number generator with entropy in s
function seed( s )
{
    var rSeed = [];
    var n = 0,nn = 0;
    while (n < s.length)
    {
        while (n < s.length && s.charCodeAt(n) <= 32) n++;
        if (n < s.length) rSeed[nn] = parseInt("0x" + s.substr(n, 2));
        n += 3;
        nn++;
    }

    var x, y, t;
    var Rs = [];
    var Rsl = rSeed.length;
    var Sr = r(256)
    var Rbits = 0

    if (Rs.length == 0)
    {for (x = 0; x < 256; x++) Rs[x] = x;}
    y = 0
    for (x = 0; x < 256; x++)
    {
        y = (rSeed[x] + s[x] + y) % 256
        t = s[x];
        s[x] = s[y];
        s[y] = t
    }
    Rx = Ry = 0;
    alert("Random seed updated. Seed size is: " + Rsl);
}
// generate a random number 0 .. 255
// uses entropy from seed
function rc()
{
    // this first bit is basically RC4
    Rx = ++Rx & 255;
    Ry = ( Rs[Rx] + Ry) & 255;
    var t = Rs[Rx];
    Rs[Rx] = Rs[Ry];
    Rs[Ry] = t;
    Sr ^= Rs[(Rs[Rx] + Rs[Ry]) & 255];

  // xor with javascripts rand, just in case there's good entropy there
    Sr ^= r(256);

    Sr ^= ror(rSeed[r(Rsl)], r(8));
    Sr ^= ror(rSeed[r(Rsl)], r(8));
    return Sr;
}
// javascript's random 0 .. n
function r( n )
{return  Math.floor(Math.random() * n);}
// rotate right
//function ror(a,b) {return b?((a<<b)|(a>>(8-b))&255):a;}
// random number between 0 .. n -- based on repeated calls to rc
function rand( n )
{
    if (n == 2)
    {
        if (! Rbits)
        {
            Rbits = 8;
            Rbits2 = rc(256);
        }
        Rbits--;
        var r = Rbits2 & 1;
        Rbits2 >>= 1;
        return r;
    }
    var m = 1, r = 0;
    while (n > m && m > 0)
    {
        m <<= 8;
        r = (r << 8) | rc();
    }
    if (r < 0) r ^= 0x80000000;
    return r % n;
}

tstval = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
*/
// functions for generating keys-----------------------------


function bgcd( uu, vv ) // return greatest common divisor
{ 
    // algorythm from http://algo.inria.fr/banderier/Seminar/Vallee/index.html
    var d, t, v = vv.concat(), u = uu.concat()
    for (; ;)
    {
        d = bsub(v, u)
        if (beq(d, [0])) return u
        if (d.length)
        {
            while ((d[0] & 1) == 0)
                d = brshift(d).a // v=(v-u)/2^val2(v-u)
            v = d
        }
        else
        {
            t = v;
            v = u;
            u = t // swap u and v
        }
    }
}

var randomNumber = function(n)
{
    return Math.round(Math.random() * n);
}


function rnum( bits )
{
    var n,b = 1,c = 0
    var a = []
    if (bits == 0) bits = 1
    for (n = bits; n > 0; n--)
    {
        if (randomNumber(2))
        {
            a[c] |= b
        }
        b <<= 1
        if (b == hanna_bx2)
        {
            b = 1;
            c++
        }
    }
    return a
}
/*
// function to generate keys
function genkey( bits, f )
{
    timerStart()
    bits = parseInt(bits) * 8
    var q,p,p1q1,n,factorMe,d,e,r
    var c,cc,ccc,pq
    q = mpp(bits);
    p = mpp(bits)
    f.p.value = p;
    f.q.value = q
    p1q1 = bmul(bsub(p, [1]), bsub(q, [1]))
    for (c = 5; c < Primes.length; c++)
    {
        e = [Primes[c]]
        d = modinverse(e, p1q1)
        if (d.length != 1 || d[0] != 0) break
    }
    f.d.value = d;
    f.e.value = e;
    f.pq.value = (pq = bmul(p, q))
 // test
    timerStop()
    c = bmod(tstval, pq)
    cc = bmodexp(c, e, pq)
    timerStart()
 //cc1=bmodexp(cc,d,pq)
    ccc = crt_RSA(cc, d, p, q)
    timerStop()
    return
}
function timerStart()
{
    startTime = new Date();
}
function timerStop()
{
    var endTime = new Date();
    document.t.howLong2.value = document.t.howLong.value
    document.t.howLong.value = (endTime.getTime() - startTime.getTime()) / 1000.0;
}
function parseArray( a )
{
    a = a.split(",")
    for (var n = 0; n < a.length; n++)
    {
        a[n] = parseInt(a[n])
    }
    return a
}

function enc( f )
{
    timerStart()
    f.text.value = rsaEncode(parseArray(f.e.value), parseArray(f.pq.value), f.text.value)
    timerStop()
}
function dec( f )
{
    timerStart()
    f.text.value = rsaDecode([parseArray(f.d.value),
        parseArray(f.p.value),
        parseArray(f.q.value)],
        f.text.value)
    timerStop()
}
*/

var Primes = [3, 5, 7, 11, 13, 17, 19,
    23, 29, 31, 37, 41, 43, 47, 53,
    59, 61, 67, 71, 73, 79, 83, 89,
    97, 101, 103, 107, 109, 113, 127, 131,
    137, 139, 149, 151, 157, 163, 167, 173,
    179, 181, 191, 193, 197, 199, 211, 223,
    227, 229, 233, 239, 241, 251, 257, 263,
    269, 271, 277, 281, 283, 293, 307, 311,
    313, 317, 331, 337, 347, 349, 353, 359,
    367, 373, 379, 383, 389, 397, 401, 409,
    419, 421, 431, 433, 439, 443, 449, 457,
    461, 463, 467, 479, 487, 491, 499, 503,
    509, 521, 523, 541, 547, 557, 563, 569,
    571, 577, 587, 593, 599, 601, 607, 613,
    617, 619, 631, 641, 643, 647, 653, 659,
    661, 673, 677, 683, 691, 701, 709, 719,
    727, 733, 739, 743, 751, 757, 761, 769,
    773, 787, 797, 809, 811, 821, 823, 827,
    829, 839, 853, 857, 859, 863, 877, 881,
    883, 887, 907, 911, 919, 929, 937, 941,
    947, 953, 967, 971, 977, 983, 991, 997,
    1009, 1013, 1019, 1021]

var sieveSize = 4000;
var sieve0 = -1 * sieveSize;
var sieve = [];

var lastPrime = 0;

function nextPrime( p ) // returns the next prime > p
{
    var n
    if (p == Primes[lastPrime] && lastPrime < Primes.length - 1)
    {
        return Primes[++lastPrime]
    }
    if (p < Primes[Primes.length - 1])
    {
        for (n = Primes.length - 2; n > 0; n--)
        {
            if (Primes[n] <= p)
            {
                lastPrime = n + 1
                return Primes[n + 1]
            }
        }
    }
    var primes = Primes.concat();
    // use sieve and find the next one
    var pp,m
    // start with p
    p++;
    if ((p & 1) == 0) p++
    for (; ;)
    {
        // new sieve if p is outside of this sieve's range
        if (p - sieve0 > sieveSize || p < sieve0)
        {
            // start new sieve
            for (n = sieveSize - 1; n >= 0; n--)
                sieve[n] = 0
            sieve0 = p
            primes = Primes.concat();
        }

        // next p if sieve hit
        if (sieve[p - sieve0] == 0)
        { // sieve miss

            // update sieve if p divisable

            // find a prime divisor
            for (n = 0; n < primes.length; n++)
            {
                if ((pp = primes[n]) && p % pp == 0)
                {
                    for (m = p - sieve0; m < sieveSize; m += pp) sieve[m] = pp
                    p += 2;
                    primes[n] = 0
                    break
                }
            }
            if (n >= primes.length)
            {
                // possible prime
                return p
            }
        }
        else
        {
            p += 2;
        }
    }

}
function divisable( n, max ) //return a factor if n is divisable by a prime less than max, else return 0
{
    if ((n[0] & 1) == 0)
        return 2
    var c = 0;
    for (c = 0; c < Primes.length; c++)
    {
        if (Primes[c] >= max)
            return 0
        if (simplemod(n, Primes[c]) == 0)
            return Primes[c]
    }
    c = Primes[Primes.length - 1]
    for (; ;)
    {
        c = nextPrime(c)
        if (c >= max)
            return 0
        if (simplemod(n, c) == 0)
            return c
    }
}

function bPowOf2( pow ) // return a bigint
{
    var r = [], n, m = Math.floor(pow / hanna_bs)
    for (n = m - 1; n >= 0; n--)
        r[n] = 0;
    r[m] = 1 << (pow % hanna_bs)
    return r;
}

function mpp( bits ) //returns a Maurer Provable Prime, see HAC chap 4 (c) CRC press
{
    if (bits < 10) return [Primes[randomNumber(Primes.length)]]
    if (bits <= 20) return [nextPrime(randomNumber(1 << bits))]
    var c = 10, m = 20, B = bits * bits / c, r, q, I, R, n, a, b, d, R2, nMinus1
    if (bits > m * 2)
    {
        for (; ;)
        {
            r = Math.pow(2, Math.random() - 1);
            if (bits - r * bits > m)
                break;
        }
    }
    else
    {
        r = 0.5
    }
    q = mpp(Math.floor(r * bits) + 1)
    I = bPowOf2(bits - 2);
    I = bdiv(I, q).q;
    var Il = I.length;
    var loopcnt = 0
//    try {
    for (; ;loopcnt++)
    {
        // generate R => I < R < 2I
        R = [];
        for (n = 0; n < Il; n++)
            R[n] = randomNumber(hanna_bx2);
        R[Il - 1] %= I[Il - 1];
        R = bmod(R, I);
        if (! R[0])
            R[0] |= 1; // must be greater or equal to 1
        R = badd(R, I);
        n = blshift(bmul(R, q), 1); // 2Rq+1
        n[0] |= 1;
        if (!divisable(n, B))
        {
            a = rnum(bits - 1);
            a[0] |= 2; // must be greater than 2
            nMinus1 = bsub(n, [1]);
            var x = bmodexp(a, nMinus1, n);
            if (beq(x, [1]))
            {
                R2 = blshift(R, 1);
                b = bsub(bmodexp(a, R2, n), [1]);
                d = bgcd(b, n);
                if (beq(d, [1]))
                    return n;
            }
        }
    }
//    } finally {
//        lucidapi.debug("loopcnt: %d", loopcnt);
//    }
}

